﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using UFPE.CIn.Abc.Primality.Util;

namespace UFPE.CIn.Abc.Primality.Algorithms
{
    public class SolovayStrassen : BaseConfidenceAlgorithm
    {
        public override string AlgorithmName
        {
            get
            {
                return "Solovay-Strassen";
            }
        }

        private static SolovayStrassen instance;

        public static SolovayStrassen Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new SolovayStrassen();
                }

                return instance;
            }
        }

        //
        // Setting probability of error to 1/2^50
        //
        public override bool IsPrime(BigInteger x)
        {
            return IsPrime(x, 50, false);
        }

        public override bool IsPrime(BigInteger x, bool pass)
        {
            return IsPrime(x, 50, pass);
        }

        //***********************************************************************
        // Probabilistic prime test based on Solovay-Strassen (Euler Criterion)
        //
        // p is probably prime if for any a < p (a is not multiple of p),
        // a^((p-1)/2) mod p = J(a, p)
        //
        // where J is the Jacobi symbol.
        //
        // Otherwise, p is composite.
        //
        // Returns
        // -------
        // True if "this" is a Euler pseudoprime to randomly chosen
        // bases.  The number of chosen bases is given by the "confidence"
        // parameter.
        //
        // False if "this" is definitely NOT prime.
        //
        //***********************************************************************

        public override bool Helper(BigInteger thisVal, int confidence)
        {
            int bits = thisVal.bitCount();
            BigInteger a = new BigInteger();
            BigInteger p_sub1 = thisVal - 1;
            BigInteger p_sub1_shift = p_sub1 >> 1;

            Random rand = new Random();

            for (int round = 0; round < confidence; round++)
            {
                bool done = false;

                while (!done)		// generate a < n
                {
                    int testBits = 0;

                    // make sure "a" has at least 2 bits
                    while (testBits < 2)
                        testBits = (int)(rand.NextDouble() * bits);

                    a.genRandomBits(testBits, rand);

                    int byteLen = a.dataLength;

                    // make sure "a" is not 0
                    if (byteLen > 1 || (byteLen == 1 && a.IsZerothBitDiffOfOne()))
                        done = true;
                }

                // check whether a factor exists (fix for version 1.03)
                BigInteger gcdTest = a.gcd(thisVal);
                if (gcdTest.dataLength == 1 && gcdTest.IsZerothBitDiffOfOne())
                    return false;

                // calculate a^((p-1)/2) mod p

                BigInteger expResult = a.modPow(p_sub1_shift, thisVal);
                if (expResult == p_sub1)
                    expResult = -1;

                // calculate Jacobi symbol
                BigInteger jacob = BigInteger.Jacobi(a, thisVal);

                //Console.WriteLine("a = " + a.ToString(10) + " b = " + thisVal.ToString(10));
                //Console.WriteLine("expResult = " + expResult.ToString(10) + " Jacob = " + jacob.ToString(10));

                // if they are different then it is not prime
                if (expResult != jacob)
                    return false;
            }

            return true;
        }
    }
}
